2018 Multi-University Training Contest 9(牛客)

补题进度：1/10
毕克大爷也出的太难了吧

---

A

题意

题解

---

B

题意

题解

---

C

题意

题解

---

D

题意

题解

---

E

题意

n局游戏，每局获胜的概率为p[i]，连续获胜的局数为x，得到的分数为x^m，问最后得分的期望值

题解

暴力的想是整个序列一共 $2^n$ 种可能
换个角度，一共有$(n+1)·n/2$个区间，若考虑出所有区间的贡献即可

• 区间 $[i,j]$ 的贡献 = $(j-1+1)^m$ × 区间[i,j]全部获胜的概率 × (i-1)失败的概率 × (j+1)失败的概率

---

F

题意

题解

---

G

题意

题解

---

H

题意

题解

---

I

题意

题解

---

J

题意

给一个长度为n的序列，和q次询问，每次询问修改一个位置的数字，对于每次询问(询问相对独立)，回答序列从第一个数开始严格上升的长度 $(1 ≤ n, q ≤ 10^5)$

题解

---

K

题意

题解

---

L

题意

题解

---

M

题意

题解

---